#include<iostream>
#include<stdexcept>

template <class T>
class Vector {
public:
  explicit Vector(int size = 0)
  :m_nSize(size),m_nCapacity(size+SPARE_CAPACITY){
      m_pElements = (T *)::operator new(m_nCapacity * sizeof(T));
  }             // creates a vector for holding 'size' elements

  Vector(const Vector& r)
  :m_nSize(r.size()) , m_nCapacity(r.m_nCapacity ){
      m_pElements = (T *)::operator new(m_nCapacity * sizeof(T));

      for (int i = 0; i < m_nSize;i++)
      {
          m_pElements[i] = r[i];
      }
  }       // the copy ctor

  Vector& operator=(const Vector&r)
  {
      Vector copy = r;
      std::swap(*this, copy);
      return *this;
  }


  ~Vector()
  {
      clear();
      ::operator delete(m_pElements, m_nCapacity * sizeof(T));
  }                     // destructs the vector

  Vector(Vector && r):m_nSize(r.m_nSize), m_nCapacity(r.m_nCapacity),m_pElements(r.m_pElements) 
  {
      r.m_nCapacity = 0;
      r.m_nSize = 0;
      r.m_pElements = nullptr;
  } //r-ref ctor

  Vector& operator=(Vector&& r)
  {
      m_nSize = r.m_nSize;
      m_nCapacity = r.m_nCapacity;
      m_pElements = r.m_pElements;
      r.m_nSize = 0;
      r.m_nCapacity = 0;
      r.m_pElements = nullptr;
      return *this;
  }  // move assignment

  T &operator[](int index) { return m_pElements[index]; } // accesses the specified element without bounds checking
  const T& operator[](int index) const{ return m_pElements[index];}
  T& at(int index)
  {
        if (index < 0 || index > m_nSize)
        {
            throw std::out_of_range("Out of range");
        }else{
            return m_pElements[index];
        }
  }              // accesses the specified element, throws an exception of type 'std::out_of_range' when index <0 or >=m_nSize
  
  int size() const { return m_nSize; } // return the size of the container
  int capacity() const { return m_nCapacity; } // return the capacity of the container


  void push_back(const T& x)
  {
      if (m_nSize >= m_nCapacity)
      {
          inflate();
      }
      m_pElements[m_nSize++] = x;
  }    // copy an element to the end 
  void push_back( T&& x)
  {
      if (m_nSize >= m_nCapacity)
      {
          inflate();
      }
      m_pElements[m_nSize++] = std::move(x);
  }    // move an element to the end 
  void pop_back(){
      if (m_nSize>0)
      {
          m_nSize--;
          m_pElements[m_nSize].~T();
      }
  } // pop the last element 

  const T& back() const{ return m_pElements[m_nSize - 1];}

  void clear()
  {
      for (int i = 0; i < m_nSize;i++)
      {
          m_pElements[i].~T();
      }
      m_nSize = 0;
  }                  // clear the contents
  bool empty() const
  {
      return (m_nSize == 0);
  }            // check whether the container is empty 

  void resize(int newSize)
  {
      if(newSize>=m_nCapacity)
      {
          inflate(2*newSize);
      }
      m_nSize  = newSize;
  }

  typedef T *iterator;
  typedef const T* const_iterator;

  iterator begin() { return m_pElements; }
  const_iterator begin()const { return m_pElements; }
  iterator end() { return &m_pElements[size()]; }
  const_iterator end() const { return &m_pElements[size()]; }

  static int SPARE_CAPACITY;

  private:
  void inflate(int newCapacity = 0 )               // expand the storage of the container to a new capacity, e.g. 2*m_nCapacity
  {
      if (newCapacity == 0)
          newCapacity = 2 * m_nCapacity;
      if (newCapacity<m_nSize)
          m_nSize = newCapacity;
      T* m_newEle = (T *)::operator new(newCapacity * sizeof(T));

      for (int i = 0; i < m_nSize;i++)
      {
          m_newEle[i] = std::move(m_pElements[i]);
      }

      clear();

      ::operator delete(m_pElements, m_nCapacity * sizeof(T));
      m_nCapacity = newCapacity;
      m_pElements = m_newEle ;
  }
  T *m_pElements = nullptr;                // pointer to the dynamically allocated storage
  int m_nSize = 0;                   // the number of elements in the container
  int m_nCapacity = 1;               // the number of elements that can be held in currently allocated storage
};
template<class T>
 int Vector<T>::SPARE_CAPACITY = 16;